The Rules of Quantum tic-tac-toe

In traditional physics an object can only exist in one place at the same time. In quantum physics there is a phenomenon called superposition where an object can exist in two places at the same time. Only after a measurement is taken of the object will the state ‘collapse’ and will the object remain in one of the places.

In traditional tic-tac-toe a move is indicated by marking a single square. In Quantum tic-tac-toe a move is indicated by marking two squares. Each quantum move is in two squares at once; a ‘super’position. Only at a later stage is determined in which of the two squares the mark will stay.

The CodeCup will introduce a 4×4 version of tic-tac-toe.

The game

Quantum tic-tac-toe is played on a 4×4 board. Players will take turns marking squares on the board. The goal of the game is to be the first player to mark an entire row, column or diagonal with your mark. The players are called ‘X’ and ‘O’, just as in traditional tic-tac-toe. Player ‘X’ always starts.

X starts by marking two different squares with ‘X’. His opponent will then mark two squares with ‘O’ (note that one or both of the squares may be the same as the squares marked with ‘X’). This way the players keep taking turns and the board is slowly filled with superpositions. Players also append the number of the turn to the move.

The superpositions on the board form a path of positions that are related to each other. Look at the board in figure 1. If at any point square A is marked with a true ‘X’ (so the superposition X1 in squares A and B collapses) this means that moves O2 (A,C) and O4 (A,F) can no longer exist in square A. So these moves also collapse into their respective squares. A series of moves has to collapse when the moves form a chain that is a cycle. In figure 1 you can see that moves X1 (A,B), X3(B,F) and O4(F,A) form such a cycle.

Whenever a player makes a move that creates the cycle his opponent has to determine in which square this last move collapses. In figure 1 the last move is ‘O’ (A,F), so player ‘X’ has to decide whether ‘O’ collapses into A or into F.  This collapse causes all fields involved with the cycle to collapse. Figure 2 shows the two possibilities for the playing field after ‘X’ has made his choice.

situation after choosing A	situation after choosing F

The game continues until a row, column or diagonal with four of the same marks is formed, or until all superpositions have collapsed and no more moves can be made. If the board has only a single uncollapsed square player ‘O’ must place both his marks in this square and then claim this square as ‘O’.

Bonus points

A player scores points by obtaining rows, columns or diagonals of length three. Each of these will give him 1 extra point. A player scores 2 bonus points for each group of 2 x 2 squares that is completely filled with his mark.

Score

If one of the players obtains a row, column or diagonal of length four the games ends immediately and this player gets 20 points. Both players keep the bonus points. Note that the winning player automatically gets 2 bonus points because the winning row, column or diagonal of length four contains two rows/columns/diagonals of length three.

It is possible that a collapse cause both players to have a row, column or diagonal of length four. Based on the subscripts of the original moves (so the time that the move was made, not the time that the move collapsed) it is determined which player would have won first. This player gets 15 points; his opponent gets 5 points. Also in this case all bonus points are added to the score.

If the game ends in a tie both players will score 10 points as well as their bonus points.

Illegal moves

If a player makes an illegal move, crashes or runs out of time, the opponent wins automatically. The player that causes the illegal game gets a score of 0. The jury software will take control of the problematic player. The jury software will search for legal moves and will make the first legal move. This enables the remaining player to still score points.

Playing the game

Your program communicates with the jury program using standard input (stdin) and standard output (stdout). Your program reads information from stdin and writes its moves to stdout.

The player that starts the game (X) will receive the word ’Start’ on stdin when the program is started. The player that plays O receives the first move of X on stdin when the program is started.

Your program should determine a move and write the move to stdout. After making a move your program should read the move of the opponent from stdin. Any move that you read from stdin is guaranteed by the judging software to be a legal move. Note that all moves will be terminated with a newline and you must flush your output.

The program must continue until the text ‘Quit’ is read on stdin. This indicates that your program has to terminate normally.

Example Game

If to the input of a player an exclamation mark (!) is added, the player first has to make a decision in a collapse. In turn 3 the X-player must make a choice between A or B before announcing CD, therefore his move is: ACD.

In the example game the O-player played an H in turn 14. Because he knew that the game was over, he needn’t had to make the announcement for two new options.

Time limit

Your program has a total playing time of 5 seconds. The jury computers use a Pentium IV, 2.8 GHz with 64 Mb of internal memory available for your program. You can decide how you divide the 5 seconds over the various moves. Your program is suspended after the system receives your output and turned to an active state when there is input for your program, only the active time is counted.

About CodeCup

CodeCup is a computer programming competition that is organized the Nederlandse Informatica Olympiade (NIO), the Dutch Olympiad in Informatics. The competition is hosted online and can be followed live on the internet. Programmers from all over the world can enter the CodeCup competition. CodeCup staff and NIO staff do not participate.

More information

Click here to see a sample game. For more information on tactics have a look at http://www.paradigmpuzzles.com/.